package 二零年3月;

import java.util.List;

/*
* 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，
* 盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上
* (即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
 输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]
示例2:
 输入：A = [1, 0], B = [], C = []
 输出：C = [1, 0]

    对于汉诺塔问题，是经典的递归题，记得自己学了几次了，还是这个样子，碰见就懵，属实没道理的，要反省了呀！
 继续再来一次吧，可以把这个问题分为什么呢，1和n-1问题，
     n=1时，直接将A移动到C就行
     n>1呢，先将n-1个盘子移动到B，然后在将最后一个盘子移动到C，接着利用递归，将这n-1个盘子移动到C
    即： 先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
         再将最大的盘子从 A 移到 C；
         再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。


     总结一下，核心思路是什么，是将问题从n转化为 n-1 + 1 的问题。
* */
public class InterView0806 {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(),A,B,C);
    }

    /**
     *
     * @param n  :A盘中剩下的个数
     * @param a  ：A盘
     * @param b  ：B盘
     * @param c  ：C盘
     */
    public void move(int n,List<Integer> a, List<Integer> b, List<Integer> c){
        //递归头，递归到最后一层，A只有一个盘子在移动后结束返回
        if(n==1){
            c.add(a.remove(a.size()-1));
            return;
        }
        move(n-1,a,c,b);  //把上面 n - 1 个盘子从 A 移到 B
        c.add(a.remove(a.size()-1)); //再将最大的盘子从 A 移到 C；
        move(n-1,b,a,c);  //再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。
    }
}
